import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Solution433 {

    static class Pair{
        String s;
        int step;

        public Pair(String s, int step) {
            this.s = s;
            this.step = step;
        }
    }

    public int minMutation(String start, String end, String[] bank) {
        Map<String,Integer> map=new HashMap<>();
        char[] chars=new char[]{'A','C','T','G'};
        for (String s : bank) {
            map.put(s,Integer.MAX_VALUE);
        }
        if (!map.containsKey(end)){
            return -1;
        }
        map.put(start,0);
        Queue<Pair> queue=new LinkedList<>();
        queue.offer(new Pair(start, 0));
        while (!queue.isEmpty()){
            Pair pair=queue.poll();
            for (int i=0;i<pair.s.length();i++){
                StringBuilder stringBuilder=new StringBuilder(pair.s);
                for (int j=0;j<4;j++){
                    stringBuilder.setCharAt(i,chars[j]);
                    if (map.getOrDefault(stringBuilder.toString(),0)==Integer.MAX_VALUE){
                        map.put(stringBuilder.toString(),pair.step+1);
                        queue.offer(new Pair(stringBuilder.toString(), pair.step + 1));
                    }
                }
            }
        }
        return map.get(end)==Integer.MAX_VALUE?-1:map.get(end);
    }

    public static void main(String[] args) {
        System.out.println(new Solution433().minMutation("AAAAACCC","AACCCCCC",new String[]{"AAAACCCC", "AAACCCCC", "AACCCCCC"}));
    }
}
